# -*- coding:utf-8 -*-


class Solution:
    """
    最长回文字符串
    使用算法：Manacher's Algorithm
    """

    def longestPalindrome(self, s):
        t = addstr(s)
        slist = list(t)
        p = list(range(len(slist) - 1))
        for i in range(0, len(p)):
            p[i] = 0
        s = judgePalindrome(slist, p, s)
        return s


def addstr(s):
    """
    修饰字符串，为回文字段检测做准备
    
    :param s: 
    :return: 
    """
    slist = list(s)
    s = "#".join(slist)
    s = "$#" + s + "#."
    return s


def judgePalindrome(slist, p, s):
    """
    检测回文字段
    
    :param slist: 
    :param p: 
    :param s: 
    :return: 
    """
    mx = 0
    sid = 0
    reslen = 0
    rescenter = 0
    for i in range(1, len(slist) - 1):
        p[i] = min(p[2 * sid - i], mx - i) if mx > i else 1
        while (slist[i + p[i]] == slist[i - p[i]]):
            p[i] += 1
        if mx < i + p[i]:
            mx = i + p[i]
            sid = i
        if reslen < p[i]:
            reslen = p[i]
            rescenter = i
    start = int((rescenter - reslen) / 2)
    str1 = s[start:start+reslen-1]
    return str1


s1 = "ccc"
s2 = "cbbd"
s3 = "abcda"
s4 = "a"
s5 = "abababababababababababababababababababababababababababababababababababababababababababababababababababab" \
     "abababababababababababababababababababababababababababababababababababababababababababababababababababa" \
     "bababababababababababababababababababababababababababababababababababababababababababababababababababab" \
     "abababababababababababababababababababababababababababababababababababababababababababababababababababab" \
     "abababababababababababababababababababababababababababababababababababababababababababababababababababab" \
     "abababababababababababababababababababababababababababababababababababababababababababababababababababab" \
     "ababababababababababababababababababababababababababababababababababababababababababababababababababababa" \
     "bababababababababababababababababababababababababababababababababababababababababababababababababababab" \
     "abababababababababababababababababababababababababababababababababababababababababababababababababababa" \
     "bababababababababababababababababababababababababababababababababa"
s = Solution()
a = s.longestPalindrome(s1)
b = s.longestPalindrome(s2)
c = s.longestPalindrome(s3)
d = s.longestPalindrome(s4)
e = s.longestPalindrome(s5)
print(a)
print(b)
print(c)
print(d)
print(e)
